Chubby

架構

下圖是一個Chubby的架構

• 分成Client與Chubby Cells
• 五個replica servers組成一個高可用的Chubby Cells提供Lock Service給Client用。
• Client透過chubby library和Chubby Service利用RPC

除了使用Chubby的為分散式系統以外，Chubby本身也是分散式系統，且為了提供上面的Client一致性的服務，Chubby Cell裡面的replica servers本身就必須是一致性的。

Chubby 內部的一致性

為了讓Chubby高可用，且支撐上千個Google內部的分散式服務，因此Chubby本身的設計也是分散式系統，理所當然就會需要共識演算法來達成一致性，且因為設計了Watch機制與事件通知機制，Chubby內部的replica servers必須是Strong Consistency。

雖然論文並沒有明說Chubby是採用哪種共識演算法，但是既然Mike Burrows本人對Paxos非常情有獨鍾，很大機率就是使用他們自己實現的Paxos且是Multi-Paxos，我們這邊做個簡介，比較與之前介紹的Paxos有什麼不同。

因此Chubby內部的一致性如下:

1. 內部的5個replica servers先經過共識演算法選出一個Master (Leader)
2. 與Paxos有多個Proposers不同
   • 這個Master只會有一個且有lease時間。也就是在此lease時間內都會只有這個Master來提出Proposer，來更新其他replica servers的訊息。
   • 就不需像原本的Paxos一樣多個Proposers每次都要兩階段提交(Prepare->Commit)過程，甚至必須競爭Proposer Number。
   • 這個Master可以不斷的向所有的replica servers commmit更新的資料。
3. Client的讀寫都是經過Master，讀直接從Master讀，寫入必須等待Master利用Paxos共識演算法同步replica server才返回寫成功。
4. Master失效的話，replica servers可以重新做Leader Election。

Paxos如果發生Partition，比方說3:2，因為2個replica servers不過半數。所以如果client對那2個servers發出請求，會顯示不可用，Availability被交換掉。只有那3個servers還可以運作Paxos協定所以可以使用。

Lock 的實作 與 File System

File, Directory 為 Node

我們先看Chubby的Interface，了解Client如何使用這個Lock Service，再來看他怎麼實作Lock。

1. Node: Chubby的底層實際上是一個分散式文件系統(Distributed File System)，提供一個類似UNIX的文件系統，因此包含了Files和Directory來存儲Data。而不管是File還是Directory都統稱為 Node，名字在系統唯一。

2. /ls/foo/wombat/pouch:

   • ls: lock service
   • foo: Chubby cell
     (5個servers組成一個Cell提供Chubby服務，Google內部有好幾個Chubby Cell)
   • /wombat/pouch: Directory 和 File Name

3. Ephemeral Node: 該Node的生命週期等於Client的連接時間，Client離線或是一個Node沒有被任意Client打開，此Node會被刪除，可以用來判斷Client是否仍然活著。另有Permanent Node

4. Handle: Clients Open/Create Node，會得到類似UNIX的File Discriptor的Handle以訪問該Node，包含:

   • check digits: 避免Client偽造或是猜到Handle
   • sequence number: Chubby Master可以用此seq來判斷這個Handle是之前的Master產生的還是自己。

Node

Node除了本質上是一個File或是Directory

Node含有以下資訊:

• Client儲存的Data
• access control lists (ACL): 讀、寫、更改ACL共3種，創建實際成自parent node，可以覆蓋。
• Instance number: 比之前創建的同名Node還大。
• Content generation number: 每當Data被更新就增加，用來判斷資料是否被更新。
• Lock generation Number: 當此Node被一個Client從Free到Held就增加，視為鎖號。
• ACL generation number: 當ACL被更新就增加。
• 64-bit file-content checksum: 比對文件內容

Node 為 Lock 的實作方法 & Sequencer

每一個Node都可以被拿來作為 advisory reader/writer lock 使用。

1. 先說Advisory與Mandatory Lock差別

   • Mandatory Lock: 當一個資源或是文件被Lock住後，其他的Client皆無法在讀取查看該文件，返回錯誤。
   • Advisory Lock: 反之，即使該資源或是文件被Lock住，Client仍然可以讀取查看該資源，因此只有當其他Client也想要取得Lock時，會出現錯誤。

   原因:

   • Chubby的Lock可能被用在其他服務的資源上，如果是Mandatory Lock，但是該服務其實允許資源被鎖住仍可讀取，則不滿足該服務的使用情境，還必須做改寫。
   • 當一個資源目前被Chubby鎖住，結果為了debug方便，使用者必須暫停Chubby服務來解鎖，才能查看資源文件狀態。
   • bug的發生，跟這個鎖允不允許使用者讀取critical section的資源不怎麼有關，因此Mandatory Lock效益不大，可以鎖就好。

2. 使用
   (1). 每一個Node都是Lock，有兩種模式 (都是Advisory Lock)

   • exclusive (writer) mode: 只限一個Client使用
   • shared (reader) mode: 多個Clients使用

   回過頭來利用Multithreading的經驗想一下什麼時候會用Lock，就是有好幾個processes都會操作共用資源時嘛。
   除了這些是平行發生的，在網路的世界中，還有訊息延遲或是亂序的情況發生。
   所以其實前面介紹ACID、DB的Transacrion、共識演算法，其實有一部份在講的是 sequentialized。
   而Chubby Lock Service最主要就是解決了這個問題，他使得使用同一個Lock的請求被 sequentialized。
   我們來看看怎麼用。

   (2). Sequencer
   舉一個簡單的例子，如果一個Key-Value Store是需要被Lock住的共享資源，我希望對這個儲存服務的操作被 sequentialized，要求對Key-Value Store的更新都必須拿到Chubby Locks才能做事。

   1. 當一個Client acquire a given lock (of a node)，他會取的該Lock(Node)的Sequencer，這個東西包含。
      • Lock的名稱(Node)
      • 是哪一種Mode(read, write)
      • Lock generation Number(Node的Metadata)，每次取得與釋放會增加，故唯一可判斷此Lock新舊。
   2. 這個client可以將此Sequencer遞給另外一個Service，表示自己拿到Lock，有這個權限。
   3. 此服務拿Sequencer再去跟Chubby比對，確認是最新合法的Lock允許了Client的操作請求。

搭配Node與Acquire Lock得到的Sequencer我們就可以實現與Multithreading一樣的Lock概念。

圖解

範例一

1. q 為Key-Value儲存服務，p為一個process。p 先向Chubby acquire 一個 Lock。
   

2. p要更新儲存的資料時，將取得Sequencer傳給 q，q去向Chubby驗整正確性與是否最新，同意請求。
   

3. 每次操作都先拿取Lock
   

以上就是很基本Chubby Lock Service使用。

範例二 - Leader Election

1. Leader Election
   如果你只是像Kafka或是Hadoop這種要選Leader，不是需要一致性資料的儲存服務，那選Leader就不用像Raft還要比較log新舊或是一對term限制。
   直接搭配Chubby就非常簡單，
   這就是一個搭配File System加上Lock Service應用的情境。

   

   1. 每一個Process都去Chubby搶著acquire "myservice/primary" Node的Lock。
   2. 誰先創建誰就可以把自己的ip寫進去，他就是Leader

   其他人只要去Watch的 "myservice/primary" Node 就可以知道現在Leader是否還活著，因為如果Leader斷線Chubby Node也會有反應跟事件通知。

夠簡單吧！

2. New/Old Leader
   那如果Old Leader失效重啟他以為自己還是Leader，仍然要求別的replica server運作呢？搭配剛剛學到的Sequencer我們就可以運作起來如下。
   Leader取得Lock也會拿到Sequencer。
   

   • 每一次通知replica servers去做事都必須把自身的Sequencer給他

   

   • replica servers拿著Sequencer去Chubby驗證，就知道這個Leader是新的還是舊的了

也很簡單吧！

小結

Chubby 其實是一個蠻強大且方便的系統，在分散式的環境中提供了很多功能，包含File System、Event-Watch、Lock Service等。

但是就像Borg或是很多Google的論文一樣，非常工程經驗導向，
有很多的名詞與定意與設計，卻又同時不開源，導致入門門檻很高。
論文有時看起來似懂非懂，希望上面的解釋搭配兩個小例子可以讓大家有點具體的印象。

如果還是不太能理解，沒關係我們之後拿Zookeeper來當例子，或是你本身有在用Zookeeper那一定非常有感，因為使用上是差不多的。

明天將要針對上面例子提到的問題，怎麼解決效能問題來介紹。

Chubby整理成筆記好難 =_=